package com.kizuki.algorithm.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 *
 * https://leetcode-cn.com/problems/pascals-triangle/
 */
public class 杨辉三角 {

    class Solution {
        public List<List<Integer>> generate(int numRows) {
            List<List<Integer>> res = new ArrayList<>();
            if (numRows <= 0) {
                return res;
            }
            res.add(Arrays.asList(1));
            for (int i = 1; i < numRows; i++) {
                List<Integer> lastRow = res.get(i - 1);
                Integer[] curRow = new Integer[lastRow.size() + 1];
                curRow[0] = curRow[lastRow.size()] = 1;
                for (int j = 1; j < curRow.length - 1; j++) {
                    curRow[j] = lastRow.get(j) + lastRow.get(j-1);
                }
                res.add(Arrays.asList(curRow));
            }
            return res;
        }
    }
}
